package week09

// 51. N 皇后
// https://leetcode-cn.com/problems/n-queens/

func solveNQueens(n int) [][]string {
	var board = make([][]byte, n)
	for i := range board {
		board[i] = make([]byte, n)
		for j := range board[i] {
			board[i][j] = '.'
		}
	}
	return dfs(board, 0, makeRecord(), makeRecord(), makeRecord(), 0, [][]string{})
}

func dfs(board [][]byte, row int, colV, leftV, rightV map[int]bool, count int, ans [][]string) [][]string {
	if row == len(board) {
		if count == len(board) {
			var res []string
			for i := range board {
				res = append(res, string(board[i]))
			}
			ans = append(ans, res)
		}
		return ans
	}
	for col := 0; col < len(board[row]); col++ {
		cv, lv, rv := colV[col], leftV[row+col], rightV[row-col]
		if cv || lv || rv {
			continue
		}
		board[row][col] = 'Q'
		colV[col], leftV[row+col], rightV[row-col] = true, true, true
		ans = dfs(board, row+1, colV, leftV, rightV, count+1, ans)
		colV[col], leftV[row+col], rightV[row-col] = cv, lv, rv
		board[row][col] = '.'
	}
	return ans
}

func makeRecord() map[int]bool {
	return make(map[int]bool)
}